A central problem in network virtualization is classification of logical flows at the source hypervisor, and acting on the classification at both source and destination hypervisors. Usually, an overlay network of tunnels carries the classification encodings across hypervisors. However some tunneling protocols (e.g. VXLAN) are not able to carry these encodings. This limits the functionality (features) available from a network virtualization solution on such overlays, and makes some other features impossible.